package 中等;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class 寻找重复的子树652 {

    private HashMap<String,Integer> map = new HashMap<>();

    private List<TreeNode> list = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return list;
    }

    //把一棵树格式化成字符串
    public String traverse(TreeNode root){
        if (root == null){
            return "#";
        }

        String left = traverse(root.left);
        String right = traverse(root.right);

        String rootStr = root.val + "-" +left + "-" + right;

        Integer num = map.getOrDefault(rootStr, 0);
        if (num == 1){
            list.add(root);
        }
        map.put(rootStr,num+1 );
        return rootStr;
    }
}
